/*
题目: 最低加油次数
汽车从起点出发驶向目的地，该目的地位于出发位置东面 target 英里处。

沿途有加油站，每个 station[i] 代表一个加油站，它位于出发位置东面 station[i][0] 英里处，并且有 station[i][1] 升汽油。

假设汽车油箱的容量是无限的，其中最初有 startFuel 升燃料。它每行驶 1 英里就会用掉 1 升汽油。

当汽车到达加油站时，它可能停下来加油，将所有汽油从加油站转移到汽车中。

为了到达目的地，汽车所必要的最低加油次数是多少？如果无法到达目的地，则返回 -1 。

注意：如果汽车到达加油站时剩余燃料为 0，它仍然可以在那里加油。如果汽车到达目的地时剩余燃料为 0，仍然认为它已经到达目的地。

https://leetcode.cn/problems/minimum-number-of-refueling-stops/description/
 */
public class MinRefuelStops {
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        // 每到达一个加油站就提桶, 但是不用, 等到油不够的时候, 挑一个最大桶的出来
        int n = stations.length;

        // TreeSet<Integer> storage = new TreeSet<> (); 不能有重复值, 所以构造大根堆
        PriorityQueue<Integer> storage = new PriorityQueue<> ((o1, o2) -> {return o2 - o1;});
        int src = 0;

        // 当前能走到哪里
        int cur = startFuel;
        for (int i = 0; i < n; i ++) {
            if (cur < stations[i][0]) {
                while (!storage.isEmpty() && cur < stations[i][0]) {
                    cur += storage.poll();
                    src ++;
                }
                if (cur < stations[i][0])
                    return -1;
            }
            storage.offer(stations[i][1]);
        }

        // 再特殊处理一下 <能否到达终点站>
        while (!storage.isEmpty() && cur < target) {
            cur += storage.poll();
            src ++;
        }
        // 总路程是否大于终点站
        return cur < target ? -1 : src;
    }
}
